Large, complex data systems may be expressed using a variety of data structures. One common data structure is a hierarchy. A hierarchy is based on an asymmetrical relationship such as “is the manager of,” “is part of,” or “is parent of.” The relationship is asymmetrical in that it only works one way. For example, Sally is the manager of Jim, but not vice versa. A hierarchy can be represented as an acyclic graph with a single root node. Such a structure is commonly referred to as a tree because it is often depicted as an upside down tree with the root node at the top and its children, grandchildren, etc., fanning out beneath it. In a tree structure, each node, except the root node, contains one ancestor (parent) node but any number of descendent (child) nodes. A tree must be acyclic, meaning there are no cycles (i.e., closed loops) in the tree. If a node is related to another node it must either be a descendent or an ancestor, but never both. In general, there is no rule that every node must have the same number of children, so a tree does not have to be symmetrical or balanced. Such a tree is referred to as “ragged hierarchy of indeterminate depth.” A common use for tree structures is to display an organization's internal structure of departments, groupings, and personnel; i.e., an organization chart. More complex trees may be used for a data center to represent the oftentimes thousands of nodes relating components of the data center. The tree structure is commonly stored in a software system using a hierarchy table. The hierarchy table may be used by an appropriate software program to construct and display all or part of the tree structure to a human user and to allow the user to navigate the tree structure. Construction of such a tree from a hierarchy table, or identification of related nodes, depending on the number of involved nodes, can be a time consuming and processor-intensive problem, because finding all of the ancestors of a given node, or all the descendents of a node requires a recursive operation. For example, to find all of the descendents of a node the system must first find all of the immediate children of the node, then find all of the children of those children (i.e. the grandchildren of the original node), then find the children of the grandchildren, and so on recursively until there are no more descendents. A similar recursive operation is necessary to find all of the ancestors of a given node, i.e., to navigate “up” the tree from a given node through all of its ancestors to the root of the tree. In Oracle™, these recursive operations are done using a hierarchical query clause, i.e., SELECT . . . FROM . . . START WITH . . . CONNECT BY. Recursive operations in general, including the above Oracle operation, present a performance problem.
A solution to the performance issue of hierarchy navigation is to use a hierarchy bridge table. A hierarchy bridge table stores all of the ancestor and descendent relationships for a given node simultaneously, allowing determination of a node's ancestors and descendents with a simple, non-recursive operation. However, the hierarchy bridge table must be kept consistent with the state of the hierarchy being represented. Maintaining consistency is complicated as nodes are inserted, deleted, and moved.